গ্রাফ ট্রাভার্সাল (Graph Traversal)
গ্রাফ ট্রাভার্সাল হল একটি প্রক্রিয়া যা গ্রাফের সকল নোড (vertices) এবং এজ (edges) পরিদর্শন করে। গ্রাফ ট্রাভার্সালের দুটি প্রধান পদ্ধতি হল ডেপথ-ফার্স্ট সার্চ (DFS) এবং ব্রেডথ-ফার্স্ট সার্চ (BFS)।
১. ডেপথ-ফার্স্ট সার্চ (DFS)
বর্ণনা
ডেপথ-ফার্স্ট সার্চ (DFS) হল একটি ট্রাভার্সাল কৌশল যা একটি নোড থেকে শুরু করে তার সর্বাধিক গভীরে প্রবেশ করে যতক্ষণ না এটি একটি শেষ নোড (leaf node) খুঁজে পায়। এরপরে এটি ব্যাকট্র্যাক করে এবং অন্য নোডগুলিতে চলে যায়। DFS সাধারণত স্ট্যাকের মাধ্যমে কার্যকর হয়।
পদ্ধতি
- শুরু নোড থেকে প্রবেশ করুন এবং তাকে ভিজিট করুন।
- সংযুক্ত নোডগুলির মধ্যে যেকোন একটি নোডে প্রবেশ করুন এবং তাকে ভিজিট করুন।
- যদি আরও সংযুক্ত নোড থাকে তবে ধাপ 2 অনুসরণ করুন।
- কোনও নোডের সকল সংযুক্ত নোড ভিজিট হয়ে গেলে ব্যাকট্র্যাক করুন।
উদাহরণ কোড (Python):
def dfs(graph, node, visited):
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
# গ্রাফের উদাহরণ
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
visited = set()
print("DFS Traversal:")
dfs(graph, 'A', visited) # Output: A B D E F C
২. ব্রেডথ-ফার্স্ট সার্চ (BFS)
বর্ণনা
ব্রেডথ-ফার্স্ট সার্চ (BFS) হল একটি ট্রাভার্সাল কৌশল যা একটি নোড থেকে শুরু করে তার সবার নিকটবর্তী নোডগুলিকে প্রথমে পরিদর্শন করে। এটি সাধারণত কিউ (queue) ডেটা স্ট্রাকচার ব্যবহার করে।
পদ্ধতি
- শুরু নোডকে কিউতে যুক্ত করুন এবং ভিজিট করুন।
- কিউ থেকে একটি নোড বের করুন এবং তার সকল নোডকে কিউতে যুক্ত করুন।
- কিউ খালি না হওয়া পর্যন্ত ধাপ 2 পুনরাবৃত্তি করুন।
উদাহরণ কোড (Python):
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=' ')
visited.add(node)
queue.extend(graph[node] - visited)
# গ্রাফের উদাহরণ
print("\nBFS Traversal:")
bfs(graph, 'A') # Output: A B C D E F
তুলনা: DFS বনাম BFS
| বৈশিষ্ট্য | DFS | BFS |
|---|---|---|
| ডেটা স্ট্রাকচার | স্ট্যাক (stack) | কিউ (queue) |
| অপেক্ষাকৃত গভীরতা | সর্বাধিক গভীরে প্রবেশ করে | প্রথমে নিকটবর্তী নোডগুলি ভিজিট করে |
| স্পেস কমপ্লেক্সিটি | O(h) (h = উচ্চতা) | O(w) (w = সর্বাধিক প্রস্থ) |
| ব্যবহার | সাইকেল খোঁজা, গাছের ট্রাভার্সাল | Shortest Path Finding |
উপসংহার
DFS এবং BFS হল গ্রাফ ট্রাভার্সালের মৌলিক পদ্ধতি যা বিভিন্ন পরিস্থিতিতে বিভিন্ন ব্যবহার রয়েছে। DFS সাধারণত গভীরতা ভিত্তিক অনুসন্ধানে ব্যবহৃত হয়, যখন BFS সর্বাধিক নিকটবর্তী নোডগুলি অনুসন্ধানের জন্য কার্যকর। প্রতিটি পদ্ধতির সময় এবং স্থান জটিলতা ভিন্ন, তাই সমস্যা অনুসারে সঠিক পদ্ধতি নির্বাচন করা গুরুত্বপূর্ণ।
Read more
